/*
 * Copyright 2010 The Scripps Research Institute
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package edu.scripps.fl.collections;

import java.util.AbstractMap;
import java.util.AbstractSet;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.SortedMap;

/**
 * A SortedMap implementation for dealing with fuzzy keys. A binary search is used to find the closest key to the input.
 * 
 * @author Mark Southern (southern at scripps dot edu). 
 */
public class FuzzyMap<K, V> extends AbstractMap<K, V> implements SortedMap<K, V> {

	protected static class ComparableComparator<T extends Comparable> implements Comparator<T> {
		public int compare(T a, T b) {
			return a == null ? (b == null ? 0 : -1) : (b == null ? 1 : a.compareTo(b));
		}
	}

	protected static class Entry<K, V> implements Map.Entry<K, V> {
		private boolean eq(Object o1, Object o2) {
			return o1 == null ? o2 == null : o1.equals(o2);
		}

		K key;

		V value;

		public Entry(K key, V value) {
			this.key = key;
			this.value = value;
		}

		public Entry(Map.Entry<K, V> e) {
			this.key = e.getKey();
			this.value = e.getValue();
		}

		public boolean equals(Map.Entry<K, V> o) {
			if (!(o instanceof Map.Entry))
				return false;
			Map.Entry<K, V> e = (Map.Entry<K, V>) o;
			return eq(getKey(), e.getKey()) && eq(getValue(), e.getValue());
		}

		public K getKey() {
			return key;
		}

		public V getValue() {
			return value;
		}

		public int hashCode() {
			return ((getKey() == null) ? 0 : getKey().hashCode()) ^ ((getValue() == null) ? 0 : getValue().hashCode());
		}

		public V setValue(V value) {
			V oldValue = this.value;
			this.value = value;
			return oldValue;
		}

		public String toString() {
			return String.format("%s [%s=%s]", getClass().getName(), getKey(), getValue());
		}
	}

	@SuppressWarnings("unchecked")
	static class MapEntryKeyComparator<K> implements Comparator {
		private Comparator<K> comparator;

		public MapEntryKeyComparator(Comparator<K> comparator) {
			this.comparator = comparator;
		}

		public int compare(Object o1, Object o2) {
			Map.Entry e = (Map.Entry) o1;
			int cmp = comparator.compare((K) e.getKey(), (K) o2);
			return cmp;
		}

		public Comparator<K> getComparator() {
			return this.comparator;
		}
	}

	private MapEntryKeyComparator<K> comparator = null;

	protected List<Map.Entry<K, V>> list = new ArrayList<Map.Entry<K, V>>();

	public FuzzyMap() {
		comparator = new MapEntryKeyComparator<K>(new ComparableComparator());
	}

	// ----------------------------------------------------------------------

	public FuzzyMap(Comparator<K> comparator) {
		this.comparator = new MapEntryKeyComparator<K>(comparator);
	}

	public FuzzyMap(Map<K, V> map) {
		loadFromMap(this, map);
	}

	@Override
	public void clear() {
		list.clear();
	}

	@Override
	public Object clone() {
		return loadFromMap(new FuzzyMap<K, V>(comparator()), this);
	}

	@Override
	public Comparator<K> comparator() {
		return comparator.getComparator();
	}

	@Override
	@SuppressWarnings("unchecked")
	public boolean containsKey(Object key) {
		int idx = Collections.binarySearch((List) list, key, comparator);
		if (idx > 0)
			return true;
		else if (idx == 0)
			return list.size() > 0 && list.get(0).getKey().equals(key) ? true : false;
		else
			return false;
	}

	// ----------------------------------------------------------------------

	@Override
	public Set<Map.Entry<K, V>> entrySet() {
		return new AbstractSet<Map.Entry<K, V>>() {
			public Iterator<Map.Entry<K, V>> iterator() {
				return list.iterator();
			}

			public int size() {
				return list.size();
			}
		};
	}

	// ----------------------------------------------------------------------

	@Override
	public K firstKey() {
		return ((Map.Entry<K, V>) list.get(0)).getKey();
	}

	@Override
	@SuppressWarnings("unchecked")
	public V get(Object key) {
		if (list.isEmpty())
			return null;
		int idx = Collections.binarySearch((List) list, key, comparator);
		if (idx < 0) {
			idx = -1 * idx - 2;
			if (idx < 0)
				idx = 0;
		}
		Map.Entry<K, V> entry = list.get(idx);
		return entry.getValue();
	}

	public Map.Entry<K, V> getEntry(int index) {
		return list.get(index);
	}

	@SuppressWarnings("unchecked")
	protected int getIndex(K key) {
		int idx = Collections.binarySearch((List) list, key, comparator);
		if (idx < 0) {
			idx = -1 * idx - 2;
			if (idx < 0)
				idx = 0;
		}
		return idx;
	}

	@Override
	public SortedMap<K, V> headMap(K toKey) {
		int idx = getIndex(toKey);
		FuzzyMap<K, V> fm = new FuzzyMap<K, V>(comparator());
		fm.list = list.subList(0, idx);
		return fm;
	}

	@Override
	public boolean isEmpty() {
		return list.isEmpty();
	}

	@Override
	public K lastKey() {
		return ((Map.Entry<K, V>) list.get(list.size() - 1)).getKey();
	}

	protected FuzzyMap<K, V> loadFromMap(FuzzyMap<K, V> fm, Map<K, V> map) {
		for (Map.Entry<K, V> entry : map.entrySet()) {
			fm.put(entry.getKey(), entry.getValue());
		}
		return fm;
	}

	@Override
	@SuppressWarnings("unchecked")
	public V put(K key, V value) {
		Entry<K, V> entry = new Entry<K, V>(key, value);
		int idx = Collections.binarySearch((List) list, key, comparator);
		if (idx >= 0) {
			Map.Entry<K, V> oldEntry = list.set(idx, entry);
			return oldEntry.getValue();
		} else {
			idx = -1 * idx - 1;
			list.add(idx, entry);
			return null;
		}
	}

	@Override
	@SuppressWarnings("unchecked")
	public V remove(Object key) {
		if (list.isEmpty())
			return null;
		int idx = Collections.binarySearch((List) list, key, comparator);
		if (idx >= 0) {
			Map.Entry<K, V> entry = list.remove(idx);
			return entry.getValue();
		}
		return null;
	}

	@Override
	public int size() {
		return list.size();
	}

	@Override
	public SortedMap<K, V> subMap(K fromKey, K toKey) {
		int idx1 = getIndex(fromKey);
		int idx2 = getIndex(toKey);
		FuzzyMap<K, V> fm = new FuzzyMap<K, V>(comparator());
		fm.list = list.subList(idx1, idx2);
		return fm;
	};

	@Override
	public SortedMap<K, V> tailMap(K fromKey) {
		int idx = getIndex(fromKey);
		FuzzyMap<K, V> fm = new FuzzyMap<K, V>(comparator());
		fm.list = list.subList(idx, list.size() - 1);
		return fm;
	}
}